package com.jiajia.study;


public class LinkedList<E> extends AbstractList<E>{

    /**
     * 头结点
     */
    private Node<E> first;

    private static class Node<E>{
        /**
         * 元素
         */
        private E element;
        /**
         * 下一个节点
         */
        private Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }

    }


    /**
     * 添加元素
     * @param element   添加的元素
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 获取某个位置的元素
     * @param index     索引位置
     * @return          元素
     */
    public E get(int index){
       return node(index).element;
    }

    /**
     * 设置 index 位置的元素
     * @param index     索引位置
     * @param element   元素
     * @return          原始位置的元素
     */
    public E set(int index,E element){
        Node<E> node = node(index);
        E oldElement = node.element;
        node.element = element;
        return oldElement;
    }

    /**
     * 往 index 位置添加元素
     * @param index     index 位置
     * @param element   元素
     */
    public void add(int index,E element){
        // 插入头结点
        if(index == 0){
            Node<E> currentNode = new Node<>(element, first);
            first = currentNode;
        }else{
            // 非头结点
            Node<E> preNode = node(index - 1);
            Node<E> currentNode = new Node<>(element, preNode.next);
            preNode.next = currentNode;
        }
        size++;
    }

    /**
     * 删除 index 位置的元素
     * @param index     index位置
     * @return          被删除的元素
     */
    public E remove(int index){
        if(size == 0){
            return null;
        }
        if(index == 0){
            Node<E> oldNode = first;
            first = null;
            size--;
            return oldNode.element;
        }

        Node<E> preNode = node(index - 1);
        Node<E> oldNode = preNode.next;
        preNode.next = preNode.next.next;
        size--;
        return oldNode.element;
    }

    /**
     * 查找元素在列表中的位置
     * @param element   元素
     * @return          位置
     */
    public int indexOf(E element){
        if(size == 0){
            return ELEMENT_NOT_FOUNT;
        }
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (element == null && node.element == null) {
                return i;
            } else if (element.equals(node.element)) {
                return i;
            }
            node = node.next;
        }
        return ELEMENT_NOT_FOUNT;
    }

    /**
     * 清空数据, size = 0,访问不到数据
     * head -> null
     */
    public void clear(){
        size = 0;
        first = null;
    }

    /**
     * 根据索引寻找节点
     * @param index 索引位置
     * @return      节点
     */
    private Node<E> node(int index){
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("位置超过了界限");
        }
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = first.next;
        }
        return node;
    }

}
